// 给定两个升序链表list1和list2，将其合并为一个升序链表

// 步骤：
// 1.使用哑结点构造一个头节点，并用cur指向它用于遍历
// 2. 判断list1和list2头节点的值，将较小的头节点加入到合并后的链表中，并向后移动该链表的头节点指针
// 3. 重复上一步，直到两个链表中出现链表为空的情况
// 4. 将剩余链表链接到合并的链表中
// 5. 将哑结点的下一个链结点作为合并后有序链表的头节点返回

// 时间复杂度：O(n)
// 空间复杂度：O(1)
const { ListNode, LinkedList } = require('../../1. 链表基础/1. 建立线性链表')

function mergeTwoLists(list1, list2) {
    let dummy_head = new ListNode(-1)
    let cur = dummy_head

    while (list1 && list2) {
        if (list1.val <= list2.val) {
            cur.next = list1
            list1 = list1.next
        } else {
            cur.next = list2
            list2 = list2.next
        }
        cur = cur.next
    }
    cur.next = list1 ? list1 : list2
    return dummy_head.next
}
let list1 = new LinkedList([1, 7, 9])
let list2 = new LinkedList([2, 4, 5, 8])
console.log(mergeTwoLists(list1.head, list2.head))